package leetCode.hw.dp;

/**
 * 动态规划解法：
 *
 * 7个苹果3个盘子有多少放法
 *
 * 定义dp[i][j]表示的是i个苹果在j个盘子的放法
 *
 */
public class HJ61Solution1 implements HJ61 {

    /**
     * 动态规划解法
     * n个盘子,m个苹果
     * @param m
     * @param n
     * @return
     */
    @Override
    public int solution(int m, int n) {
        int[][] dp = new int[n+1][m+1];
        for(int j=1;j<=m;j++) {
            dp[1][j] = 1;
        }
        for(int i=1;i<=n;i++) {
            dp[i][1] = 1;
            dp[i][0] = 1;
        }
        for(int j=2;j<=m;j++) {
            for(int i=2;i<=n;i++) {
                if(i>j){
                    dp[i][j] = dp[i-1][j];
                }
                else {
                    dp[i][j] = dp[i-1][j]+dp[i][j-i];
                }
            }
        }
        return dp[n][m];
    }

    /**
     * 放苹果递归解法
     * n个盘子,m个苹果
     * 设f(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，
     * 当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)　　
     * 当n<=m：不同的放法可以分成两类：
     * 1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);
     * 2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n) = f(m-n,n).
     * 而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)
     * 递归出口条件说明：
     * 当n=1时，所有苹果都必须放在一个盘子里，所以返回１；
     * 当没有苹果可放时，定义为１种放法；
     * 递归的两条路，第一条n会逐渐减少，终会到达出口n==1;
     * 第二条m会逐渐减少，因为n>m时，我们会return f(m,m)　所以终会到达出口m==0．
     * @param m 苹果数量
     * @param n 盘子数量
     * @return
     */
    public int solution2(int m,int n) {
        // 盘子数量不大于1的时候
        if(n <= 1) return n;
        // 有盘子但是苹果数不大于1
        if(m <= 1) return 1;
        // 当盘子数量大于苹果数量
        if(n>m) return solution2(m,m);
        // 当盘子数量小于等于苹果数量
        return solution2(m,n-1) + solution2(m-n,n);
    }

    public static void main(String[] args) {
        System.out.println(new HJ61Solution1().solution(7,3));
        System.out.println(new HJ61Solution1().solution2(7,3));
    }

}
